#include<stdio.h>
long long c(int down,int up);
long long stair(int a);
int main(void)
{
	int T,n,two,three;
	long long sum;
	scanf("%d",&T);
	for(int i=0;i<T;i++)
	{
		sum=1;
		scanf("%d",&n);
		two=n/2;
		three=n/3;
		for(int i=1;i<=two;i++)
		{
			sum+=c(n-i,i);
		}
		for(int i=1;i<=three;i++)
		{
			sum+=c(n-2*i,i);
		}
		printf("%lld\n",sum);
	}
	
	return 0;
}
long long c(int down,int up)
{
	return stair(down)/stair(up)/stair(down-up);
}
long long stair(int a)
{
	if(a==0||a==1)
	{
		return 1;
	}
	else
	{
		return a*stair(a-1);
	}
}
